package com.kjc.demo.basic.test;

public class KMPDEMO {
	/* 为避免和匹配时的i、j混淆，这里使用m、n */
	//参数是字符串
	public static int[] getNext(String T) {
	    int next[] = new int[T.length()];//定义了一个整型数组，长度伟字符串的长度
	    int m = 0;//初始化一个变量m
	    int n = -1;//初始化一个变量n
	    next[0] = -1;//初始化下标第一个元素伟-1
	    while (m < T.length() - 1) {//如果变量m一直小于字符串的长度，就一直循环，直到m大于字符串的长度
	        if (n == -1 || T.charAt(m) == T.charAt(n)) {//如果n为-1或者字符串m 等于字符串n
	            m++;//m自增
	            n++;//n自增
	            if (T.charAt(m) != T.charAt(n)) {//如果m下标的字符不等于n下标的字符
	                next[m] = n;//next 数组，m下标对应的值为n
	            } else {
	                next[m] = next[n]; //否则m下标对应的值 等于n下标对应的值
	            }
	        } else {
	            n = next[n];//0
	        }
	    }
	    return next;
	}
	
	public static int KMP(String S, String T, int pos) {
	    int i = pos - 1;
	    int j = -1;
	    int next[] = getNext(T);
	    while (i < S.length() && j < T.length()) {
	        if (j == -1 || S.charAt(i) == T.charAt(j)) {
	            i++;
	            j++;
	        } else {
	            j = next[j];
	        }
	    }
	    if (j == T.length()) {
	        return i - T.length();
	    } else {
	        return -1;
	    }
	}
	
	public static void main(String[] args) {
		
		System.out.println(KMP("abcabcabx", "abcabx", 0));
		
		int[] arr = getNext("abcabx");
		System.out.println(arr);
		for(int i= 0 ;i < arr.length ; i++) {
			System.out.print(arr[i]);
		}
	}
}
